package main.leetcode.primary.from001to100;

/**
 * 32.最长有效括号
 *
 * <p>给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 *
 * <p>示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"
 *
 * <p>示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex32 {
    public static void main(String[] args) {
        System.out.println(new ex32().longestValidParentheses(")()()"));
        System.out.println(new ex32().longestValidParentheses("()()"));
        System.out.println(new ex32().longestValidParentheses("(())"));
        System.out.println(new ex32().longestValidParentheses("(())("));
        System.out.println(new ex32().longestValidParentheses("(())()"));
        System.out.println(new ex32().longestValidParentheses("(())(()"));
        System.out.println(new ex32().longestValidParentheses("(()"));
        System.out.println(new ex32().longestValidParentheses("(("));
        System.out.println(new ex32().longestValidParentheses("(()("));
        System.out.println(new ex32().longestValidParentheses(")(((((()())()()))()(()))("));
        System.out.println(new ex32().longestValidParentheses("(()(((()"));
    }

    // 暴力法
    //    public int longestValidParentheses(String s) {
    //        int maxLen = 0;
    //        for (int i = 0; i < s.length(); ++i) {
    //            for (int j = i + 2; j <= s.length(); j += 2) {
    //                if (isValid(s, i, j)) {
    //                    maxLen = Math.max(maxLen, j - i);
    //                }
    //            }
    //        }
    //        return maxLen;
    //    }
    //
    //    private boolean isValid(String s, int i, int j) {
    //        Stack<Character> stack = new Stack<>();
    //        for (; i < j; ++i) {
    //            if (s.charAt(i) == '(') {
    //                stack.push('(');
    //            } else if (!stack.isEmpty()) {
    //                stack.pop();
    //            } else {
    //                return false;
    //            }
    //        }
    //        return stack.isEmpty();
    //    }

    // dp
    //    public int longestValidParentheses(String s) {
    //        int[] dp = new int[s.length()];
    //        int res = 0;
    //        for (int i = 1; i < s.length(); ++i) {
    //            if (s.charAt(i) == ')') {
    //                if (s.charAt(i - 1) == '(') {
    //                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
    //                } else if (i - dp[i - 1] > 0
    //                        && s.charAt(i - dp[i - 1] - 1) == '(') { // 当前“）”匹配上的“（”
    //                    // “ 0 2 0 0 2 4 ”
    //                    // “ ( ) ( ( ) ) ”
    //                    // “ 0 2 0 0 2 4 ”
    //                    // 假设当前i匹配上了最后一个“）”
    //                    dp[i] =
    //                            dp[i - 1] // 前面的有效括号长度
    //                                    + ((i - dp[i - 1]) >= 2
    //                                            ? dp[i - dp[i - 1] - 2]
    //                                            : 0) // 越过前面这串有效括号，看前面是否能匹配上之前的“（”
    //                                    + 2; // 加上自己匹配上的
    //                }
    //                res = Math.max(res, dp[i]);
    //            }
    //        }
    //        return res;
    //    }

    // 栈
    //    public int longestValidParentheses(String s) {
    //        int res = 0;
    //        Stack<Integer> stack = new Stack<>();
    //        stack.push(-1);
    //        for (int i = 0; i < s.length(); ++i) {
    //            if (s.charAt(i) == '(') {
    //                stack.push(i);
    //            } else {
    //                stack.pop();
    //                if (stack.isEmpty()) {
    //                    // 存入下标，便于做差
    //                    stack.push(i);
    //                } else {
    //                    res = Math.max(res, i - stack.peek());
    //                }
    //            }
    //        }
    //        return res;
    //    }

    // 不需额外空间
    public int longestValidParentheses(String s) {
        int res = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++left;
            } else {
                ++right;
            }
            if (left == right) {
                res = Math.max(res, left << 1);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            if (s.charAt(i) == '(') {
                ++left;
            } else {
                ++right;
            }
            if (left == right) {
                res = Math.max(res, left << 1);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return res;
    }
}
